package com.wlr.study.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class LeetCode153 {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (r + l) / 2;
            if (nums[l] > nums[mid]) {
                r--;
            } else if (nums[r] < nums[mid]) {
                l++;
            } else {
                break;
            }
        }
        return nums[l];
    }

    /**
     * 官方题解
     *
     * @param nums 数组
     * @return 查找元素
     */
    public int findMin1(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }

    public int findMin2(int[] nums) {
        Deque<Integer> deque = new ArrayDeque<>();
        int result = 0;
        for (int num : nums) {
            if (!deque.isEmpty() && deque.peek() > num) {
                result = num;
                break;
            } else {
                deque.push(num);
            }
        }
        if (deque.size()==nums.length){
            return deque.peekLast();
        }
        return result;
    }

    public static void main(String[] args) {
        LeetCode153 leetCode153 = new LeetCode153();
        int[] arr = new int[]{11, 13, 15, 17};
        System.out.println(leetCode153.findMin2(arr));
    }
}
